import java.util.Arrays;

/**
 * Created by L.jp
 * Description:给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * User: 86189
 * Date: 2021-11-25
 * Time: 20:30
 */
public class SurroundedArea {
    public void dfs(char[][] board,int row,int col,int x,int y){
        if((x<0 || x>=row || y<0 || y>=col) || board[x][y]!='O'){//当越界时或者遍历到的点不是'0’，就可以停止搜索
            return ;
        }
        board[x][y]='*';//当前的位置是'O',与边界'0'直接或者间接相连的时候,先标记这个'O'，因为不用改它
        //搜索周围四个，看是否有相连的'O'
        dfs(board,row,col,x-1,y);
        dfs(board,row,col,x,y+1);
        dfs(board,row,col,x+1,y);
        dfs(board,row,col,x,y-1);
    }
    public void solve(char[][] board) {
        int row=board.length;
        int col=board[0].length;
        //第一步，找到边界上的O,有四个边界
        //寻找第一行和最后一行的'0'
        for(int j=0;j<col;j++){
            if(board[0][j]=='O'){
                dfs(board,row,col,0,j);
            }
            if(board[row-1][j]=='O'){
                dfs(board,row,col,row-1,j);
            }
        }
        //寻找第一列和最后一列的‘O'
        for(int i=0;i<row;i++){
            if(board[i][0]=='O'){
                dfs(board,row,col,i,0);
            }
            if(board[i][col-1]=='O'){
                dfs(board,row,col,i,col-1);
            }
        }
        //寻找被包围的’0‘
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++) {
                if(board[i][j]=='*'){//把之前标记的‘O'给换回来
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }
}
